//
//  LinkedList.swift
//  LeetCodeSwift
//
//  Created by XFB on 2019/8/8.
//  Copyright © 2019 XFB. All rights reserved.
//

import Foundation

/// 将Node类的声明 更改为通用类型 T
public class Node<T> {
    /// 你的目标是允许Node类接受任何类型的值。因此将value属性定义为泛型T 而不是String
    var data: T
    var next: Node<T>?
    /// 前驱节点
    weak var previous: Node<T>?
    
    /// 将构造器更新为任意接受类型T
    public init(data: T) {
        self.data = data
    }
}

/// 链表 数据域 指针域
public class LinkedList<T> {
    
    /// 头节点
    var head: Node<T>?
    /// 尾节点
    var tail: Node<T>?
    
    /// 检测链表是否为空
    var isEmpty: Bool {
        return head == nil
    }
    
    /// 首节点
    var first: Node<T>? {
        return head
    }
    
    /// 尾节点
    var last: Node<T>? {
        return tail
    }
    
    func append(data: T) {
        
        let newNode = Node.init(data: data)
        
        if let tailNode = tail {
            newNode.previous = tailNode
            tailNode.next = newNode
        } else {
            head = newNode
        }
        tail = newNode
    }
    
//    func insertIndexAt(_ data: T, at index: Int) {
//        let newNode = Node.init(data: data)
//        insert(newNode, at: index)
//    }
    
//    func insert(_ newNode: Node, at index: Int)  {
//        if index == 0 {
//            newNode.next = head
//            head?.previous = newNode
//            head = newNode
//        } else {
//            let prev = nodeIndexAt(index: index - 1)
//            let next = prev?.next
//
//        }
//    }
    
    
    /// 通过索引来访问节点
    func nodeIndexAt(index: Int) -> Node<T>? {
        
        assert(head != nil, "List is Empty")
        assert(index > 0, "index must be greater or equal to 0")
       
        if index > 0 {
            var node = head
            var i = index
            while node != nil {
                if i == 0 {
                    return node
                }
                i = i - 1
                node = node!.next
            }
        }
        return nil
    }
    
    // MARK: - 删除所有的节点
    func removeAllNode() {
        head = nil
        tail = nil
    }
    
    // MARK: - 删除单个节点
    func remove(node: Node<T>) -> T {
       
        /// 双链表删除节点
        /// 1、删除链表第一个节点 head指针和previous指针需要更新
        /// 2、删除链表中间的一个节点 previous指针和next指针需要更新
        /// 3、删除链表的最后一个节点 next指针和tail指针需要更新
        let prev = node.previous
        let next = node.next
        
        if let prev = prev {
            /// 如果移除的不是链表的第一个节点，更新next指针
            prev.next = next
        } else {
            /// 如果移除链表的第一个节点，那么就更新head指针
            head = next
        }
        /// 将previous指针指向被移除的节点的previous
        next?.previous = prev
        
        /// 如果移除的是链表的最后一个节点，那么就更新tail指针
        if next == nil {
            tail = prev
        }
        
        /// 将移除的节点的previous和next指针置为nil
        node.previous = nil
        node.next = nil
        
        /// 返回移除的节点
        return node.data
    }
}

extension LinkedList: CustomStringConvertible {
    public var description: String {
        var text = "["
        var node = head
        
        while node != nil {
            text += "\(String(describing: node?.data))"
            node = node!.next
            if node != nil { text += ", " }
        }
        return text + "]"
    }
}
